package drawset;

import java.awt.Point;
import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class DrawSet {

	public enum Direction {
		north_west,
		north,
		north_east,
		east,
		south_east,
		south,
		south_west,
		west,
		center
	}
	
	public static final 	Set<Point>	emptySet()	{	return new HashSet<Point>();		}
	
	public static final 	Set<Point>	getCol(int x, int y, int h) {
		Set<Point>	S = emptySet();
		int			i;
		
		for(i=0; i<h; i++) {
			S.add(new Point(x,y+i));
		}
		return S;
	}
	public static final 	Set<Point>	getRow(int x, int y, int w) {
		Set<Point>	S = emptySet();
		int			i;
		
		for(i=0; i<w; i++) {
			S.add(new Point(x+i,y));
		}
		return S;
	}
	
	public static final		Set<Point>	getPoint(int x, int y) {
		return getPoint(new Point(x,y));
	}
	
	public static final		Set<Point>	getPoint(Point P) {
		Set<Point>	S = emptySet();
		S.add(P);
		return S;
	}
	
	public static final 	Set<Point>	getLine(int x0, int y0, int x1, int y1) {
		int 		dx = Math.abs(x1-x0);
		int 		dy = Math.abs(y1-y0);
		int 		sx, sy, err, e2;
		Set<Point>	S = emptySet();
		
		if (x0 < x1) {	sx = 1;	}	else	{ sx = -1;	}
		if (y0 < y1) {	sy = 1;	}	else	{ sy = -1;	}
		err = dx-dy;
		 
		   
		while(true) {
			S.add(new Point(x0,y0));
			if ((x0 == x1) && (y0 == y1))	break;
			e2 = 2*err;
			if (e2 > -dy) { 
				err = err - dy;
				x0 = x0 + sx;
			}
			if ((x0 == x1) && (y0 == y1)) {
				S.add(new Point(x0,y0));
				break;
			}
			if (e2 < dx) { 
				err = err + dx;
				y0 = y0 + sy; 
			}
		}
		return S;
	}
	
	public static final		Set<Point>	getPointRect(int x1, int y1, int x2, int y2) {
		int dx = Math.abs(x2-x1);
		int dy = Math.abs(y2-y1);
		int sx = Math.min(x1, x2);
		int sy = Math.min(y1, y2);
		return getRect(sx,sy,dx+1,dy+1);
	}

	public static final		Set<Point>	getPointRectEdge(int x1, int y1, int x2, int y2) {
		int dx = Math.abs(x2-x1);
		int dy = Math.abs(y2-y1);
		int sx = Math.min(x1, x2);
		int sy = Math.min(y1, y2);
		return getRectEdge(sx,sy,dx+1,dy+1);
	}
	
	public static final		Set<Point>	getPointRectFill(int x1, int y1, int x2, int y2) {
		int dx = Math.abs(x2-x1);
		int dy = Math.abs(y2-y1);
		int sx = Math.min(x1, x2);
		int sy = Math.min(y1, y2);
		return getRectFill(sx,sy,dx+1,dy+1);
	}
	
	public static final		Set<Point>	getRect(int x, int y, int w, int h) {
		Set<Point>	S = emptySet();
		S.addAll(getRectEdge(x,y,w,h));
		S.addAll(getRectFill(x,y,w,h));
		return S;
	}
	
	public static final 	Set<Point>	getRectEdge(int x, int y, int w, int h) {
		Set<Point>	S = emptySet();
		int			col, row;
		
		if (w<0) {
			x += w;
			w = -w;
		}
		if (h<0) {
			y += h;
			h = -h;
		}

		for(row=0; row<h; row++) {
			S.add(new Point(x,row+y));
			S.add(new Point(x+w-1,row+y));
		}
		for(col=0; col<w; col++) {
			S.add(new Point(col+x,y));
			S.add(new Point(col+x,y+h-1));
		}
		return S;
	}
	public static final		Set<Point>	getRectFill(int x, int y, int w, int h) {
		int 		col, row;
		Set<Point>	S = emptySet();
		
		if (w<0) {
			x += w;
			w = -w;
		}
		if (h<0) {
			y += h;
			h = -h;
		}
		
		for(col=x+1; col < x+w-1; col++) {
			for(row = y+1; row < y+h-1; row++) {
				S.add(new Point(col,row));
			}
		}
		return S;
	}
	public static final		Set<Point>	getCircleEdge(int x0, int y0, int r) {
		int 		x = r, y = 0;
		int 		radiusError = 1-x;
		Set<Point>	S = emptySet();
		 
		while(x >= y) {
			S.add(new Point(x + x0, y + y0));
			S.add(new Point(y + x0, x + y0));
			S.add(new Point(-x + x0, y + y0));
			S.add(new Point(-y + x0, x + y0));
			S.add(new Point(-x + x0, -y + y0));
			S.add(new Point(-y + x0, -x + y0));
			S.add(new Point(x + x0, -y + y0));
			S.add(new Point(y + x0, -x + y0));
			y++;
			if(radiusError<0) {
				radiusError+=2*y+1;
			} else {
				x--;
				radiusError+=2*(y-x+1);
			}
		}
		return S;
	}
	public static final		Set<Point>	getCircleFill(int x0, int y0, int r) {
		return getFill(getCircleEdge(x0,y0,r), x0, y0);
	}
	public static final		Set<Point>	getCircle(int xo, int y0, int r) {
		Set<Point>	S = emptySet();
		S.addAll(getCircleEdge(xo, y0, r));
		S.addAll(getCircleFill(xo, y0, r));
		return S;
	}

	public static final Set<Point>	getFill(Set<Point> S, int startX, int startY) {
		return getFill_DFS( S, startX, startY);
	}
	public static final Set<Point>	getFill_BFS(Set<Point> S, int startX, int startY) {
		Set<Point>			visited = emptySet();
		ArrayList<Point>	fringe	= new ArrayList<Point>();
		Point				P = new Point(startX, startY);
		
		fringe.add(P);
			
		while(!fringe.isEmpty()) {
			P = fringe.remove(0);
			if (!S.contains(P) && !visited.contains(P)) {
				visited.add(P);
				fringe.addAll(getAdjacent(P));
			}
		}
		return visited;
	}
	public static final Set<Point>	getFill_DFS(Set<Point> S, int startX, int startY) {
		Set<Point>			visited = emptySet();
		ArrayList<Point>	fringe	= new ArrayList<Point>();
		Point				P = new Point(startX, startY);
		
		fringe.add(P);
			
		while(!fringe.isEmpty()) {
			P = fringe.remove(fringe.size()-1);
			if (!S.contains(P) && !visited.contains(P)) {
				visited.add(P);
				fringe.addAll(getAdjacent(P));
			}
		}
		return visited;
	}
	public static final Set<Point>	getEdge(Set<Point> S) {
		Set<Point>			S2 = emptySet();
		Iterator<Point>		itr = S.iterator();
		Point				P, north, south, east, west;
		
		while(itr.hasNext()) {
			P = itr.next();
			north = new Point(P.x, P.y-1);
			south = new Point(P.x, P.y+1);
			east = new Point(P.x+1, P.y);
			west = new Point(P.x-1, P.y);
			
			if (!S.contains(north))	{	S2.add(north);	}
			if (!S.contains(south))	{	S2.add(south);	}
			if (!S.contains(east))	{	S2.add(east);	}
			if (!S.contains(west))	{	S2.add(west);	}
		}
		return S2;
	}
	public static final Set<Point>	getAdjacent(Point P) {
		Set<Point>	S = emptySet();
		S.add( new Point(P.x, P.y-1) );
		S.add( new Point(P.x, P.y+1) );
		S.add( new Point(P.x+1, P.y) );
		S.add( new Point(P.x-1, P.y) );
		return S;
	}
	public static final int pDist(int x1, int y1, int x2, int y2) {
		return Math.max(Math.abs(x2-x1), Math.abs(y2-y1));
	}
	public static final int rDist(int x1, int y1, int x2, int y2) {
		int dx = x2-x1;
		int	dy = y2-y1;
		return (int) Math.sqrt(dx*dx+dy*dy);
	}
	
	
	public static final Point getDirection(Direction D, Point P) {
		if (D == Direction.north) {
			return getN(P);
		} else if (D==Direction.north_east) {
			return getNE(P);
		} else if (D==Direction.east) {
			return getE(P);
		} else if (D==Direction.south_east) {
			return getSE(P);
		} else if (D==Direction.south) {
			return getS(P);
		} else if (D==Direction.south_west) {
			return getSW(P);
		} else if (D==Direction.west) {
			return getW(P);
		} else if (D==Direction.north_west) {
			return getNW(P);
		} else {
			return P;
		}
	}
	
	public static final Point getN(Point P) 	{	return new Point(P.x, P.y-1);	}
	public static final Point getNE(Point P)	{	return new Point(P.x+1, P.y-1);	}
	public static final Point getE(Point P)		{	return new Point(P.x+1, P.y);	}
	public static final Point getSE(Point P)	{	return new Point(P.x+1, P.y+1);	}
	public static final Point getS(Point P)		{	return new Point(P.x, P.y+1);	}
	public static final Point getSW(Point P)	{	return new Point(P.x-1, P.y+1);	}
	public static final Point getW(Point P)		{	return new Point(P.x-1, P.y);	}
	public static final Point getNW(Point P)	{	return new Point(P.x-1, P.y-1);	}
	
	public static final Point getPoint(Direction D, Rectangle R) {
		if (D==Direction.north_west) {
			return new Point(R.x, R.y);
		} else if (D==Direction.north) {
			return new Point(R.x+R.width/2, R.y);
		} else if (D==Direction.north_east) {
			return new Point(R.x+R.width, R.y);
		} else if (D==Direction.east) {
			return new Point(R.x+R.width, R.y+R.height/2);
		} else if (D==Direction.south_east) {
			return new Point(R.x+R.width, R.y+R.height);
		} else if (D==Direction.south) {
			return new Point(R.x+R.width/2, R.y+R.height);
		} else if (D==Direction.south_west) {
			return new Point(R.x, R.y+R.height);
		} else if (D==Direction.west) {
			return new Point(R.x, R.y+R.height/2);
		} else if (D==Direction.center) {
			return new Point(R.x+R.width/2, R.y+R.height/2);
		} else {
			return null;
		}
	}
}
